package DP;

import java.util.List;

/**
 * @author chenhong
 * @version 1.0
 * @description TODO
 * @date 2023/4/18 23:39
 */
public class L120 {
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < i ; j++) {
                    int cur = triangle.get(i).get(j);
                    triangle.get(i).set(j, cur + Math.min(triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1)));
                }
                triangle.get(i).set(0, triangle.get(i).get(0) + triangle.get(i - 1).get(0));
                triangle.get(i).set(i, triangle.get(i).get(i) + triangle.get(i - 1).get(i - 1));
            }
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                ans = Math.min(ans, triangle.get(n-1).get(i));
            }
            return ans;
        }
}
